package code_rhapsody.array;

/**
 * @author Synhard
 * @version 1.0
 * @class Code4
 * @description 69. x 的平方根
 * 实现 int sqrt(int x) 函数。
 *
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 *
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 *
 * 示例 1:
 *
 * 输入: 4
 * 输出: 2
 * 示例 2:
 *
 * 输入: 8
 * 输出: 2
 * 说明: 8 的平方根是 2.82842...,
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-22 8:24
 */
public class Code4 {
    public static void main(String[] args) {

    }

    public int mySqrt(int x) {
        if (x == 1) {
            return 1;
        }
        long low = 0, high = (x >> 1) + 1, mid;
        while (low + 1 != high) {
            mid = (low + high) >> 1;
            if (mid * mid < x) {
                low = mid;
                continue;
            }
            if (mid * mid > x) {
                high = mid;
                continue;
            }
            return (int) mid;
        }
        return (int) low;
    }
}
